#pragma warning(disable:4996)
#pragma warning(disable:6031)

#include <iostream>
using namespace std;

//int _QuickSort(int* arr, int left, int right)
//{
//	int keyi = left++;
//	while (left <= right)
//	{
//		while (left <= right && arr[right] > arr[keyi])
//		{
//			right--;
//		}
//		while (left <= right && arr[left] < arr[keyi])
//		{
//			left++;
//		}
//		if (left <= right)
//		{
//			swap(arr[left++], arr[right--]);
//		}
//	}
//	swap(arr[right], arr[keyi]);
//	return right;
//}

//int _QuickSort(int* arr, int left, int right)
//{
//	int key = arr[left];
//	int hole = left;
//	while (left < right)
//	{
//		while (left < right && arr[right] >= key)
//		{
//			right--;
//		}
//		arr[hole] = arr[right];
//		hole = right;
//		while (left < right && arr[left] <= key)
//		{
//			left++;
//		}
//		arr[hole] = arr[left];
//		hole = left;
//	}
//	arr[hole] = key;
//	return hole;
//}

//int _QuickSort(int* arr, int left, int right)
//{
//	int keyi = left;
//	int prev = left;
//	int cur = left + 1;
//	while (cur <= right)
//	{
//		if (arr[cur] < arr[keyi] && ++prev != cur)
//		{
//			swap(arr[cur], arr[prev]);
//		}
//		cur++;
//	}
//	swap(arr[prev], arr[keyi]);
//	return prev;
//}
//
//void QuickSort(int* arr, int left, int right)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int key = _QuickSort(arr, left, right);
//
//	QuickSort(arr, left, key - 1);
//	QuickSort(arr, key + 1, right);
//}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;
	int key = arr[left];
	int cur = left + 1;

	while (cur <= right)
	{
		if (arr[cur] < key)
		{
			swap(arr[cur++], arr[left++]);
		}
		else if (arr[cur] > key)
		{
			swap(arr[cur], arr[right--]);
		}
		else
		{
			cur++;
		}
	}

	QuickSort(arr, begin, left - 1);
	QuickSort(arr, right + 1, end);
}

int main()
{
	int arr[] = { 5,1,8,4,0,0,2,4,6,6,9,7,1,5,3 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	QuickSort(arr, 0, sz - 1);

	for (int i = 0; i < sz; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;
	return 0;
}